package com.xzz.sort;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @author: hhz
 * @create: 2021-12-30 09:33
 * 870. 优势洗牌
 * 给定两个大小相等的数组A和B，A 相对于 B 的优势可以用满足A[i] > B[i]的索引 i的数目来描述。
 *
 * 返回A的任意排列，使其相对于 B的优势最大化。
 *
 **/
public class AdvantageCount {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(advantageCount(new int[]{2, 7, 11, 15}, new int[]{1, 10, 4, 11})));
        System.out.println(Arrays.toString(advantageCount(new int[]{12, 24, 8, 32}, new int[]{13, 25, 32, 11})));
    }

    public static int[] advantageCount(int[] nums1, int[] nums2) {
        int[] res = new int[nums1.length];
        //升序排序
        Arrays.sort(nums1);
        //给nums2降序排序 但不想改变nums2的相对位置
        PriorityQueue<int[]> maxQueue = new PriorityQueue<>((int[] o1, int[] o2) -> o2[1]-o1[1]);
        for (int i = 0; i < nums2.length; i++) {
            maxQueue.offer(new int[]{i,nums2[i]});
        }
        int left = 0;
        int right = nums1.length-1;
        while (!maxQueue.isEmpty()){
            int[] poll = maxQueue.poll();
            int index = poll[0];
            int maxVal = poll[1];
            if(nums1[right]>maxVal){
                res[index] = nums1[right];
                right--;
            }else {
                res[index] = nums1[left];
                left++;
            }
        }
        return res;

    }
}
